package leetcode.editor.week.week305;

public class Solution6137 {
    // https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/solution/java-6137-jian-cha-shu-zu-shi-fou-cun-za-mrr1/
    public boolean validPartition(int[] nums) {
        boolean[] dp = new boolean[ nums.length + 1];
        int len = nums.length;
        // 题目len >= 2
        dp[0] = true;   // 初始化
        for (int i = 2; i <= len; i++) {
            // 子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
            if (nums[i - 1] == nums[i - 2]) {
                dp[i] = dp[i - 2];
            }

            // 子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
            if (i >= 3 && nums[i - 3] == nums[i - 2] && nums[i - 2] == nums[i - 1]) {
                // 注意别覆盖前面满足的情况
                dp[i] = dp[i] || dp[i - 3];
            }

            // 子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。
            if (i >= 3 && nums[i - 3] + 1 == nums[i - 2] && nums[i - 2] + 1 == nums[i - 1]) {
                // 注意别覆盖前面满足的情况
                dp[i] = dp[i] || dp[i - 3];
            }
        }

        return dp[len];
    }
}
